package com.eddie.linkedlist;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Random;
import java.util.Stack;


public class TEST {

    public static void main(String[] args) {
//        ListNode listNode = removeNthFromEnd(new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))), 1);
//        while (listNode != null) {
//            System.out.println(listNode.val);
//            listNode = listNode.next;
//        }
//        ListNode listNode1 = addTwoNumbers(new ListNode(2, new ListNode(4, new ListNode(3))), new ListNode(5, new ListNode(6, new ListNode(4))));
//        while (listNode1!=null) {
//            System.out.print(listNode1.val);
//            listNode1=listNode1.next;
//        }
//        int[] ints = twoSum(new int[]{3,2,4}, 6);
//        System.out.println(3/2);
//        for (int anInt : ints) {
//            System.out.println(anInt);
//        }
//        int i = searchInsert(new int[]{1, 3, 5, 6}, 5);
//        System.out.println(i);
        char[] strs = new char[]{'f', 'f', ' '};
        StringBuilder builder = new StringBuilder();
        for (char str : strs) {
            if (str == ' ') {
                builder.append("%20");
                continue;
            }
            builder.append(str);
        }
        System.out.println(builder);
    }

    public int[] reversePrint(ListNode head) {
        int[] arr = new int[getLength(head)];
        for(int i=0;i<arr.length;i++) {
            if(head!=null){
                arr[i]=head.val;
                head = head.next;
            }
        }
        return arr;
    }


    public static int searchInsert(int[] nums, int target) {

        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }


    public static int[] twoSum(int[] nums, int target) {

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] + num == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        String l1Str = reaser(l1);
        String l2Str = reaser(l2);
        String sum = String.valueOf(new BigInteger(l1Str).add(new BigInteger(l2Str)).longValue());
        ListNode node = new ListNode(0);
        ListNode cur = node;
        for (int i = sum.length() - 1; i >= 0; i--) {
            cur.next = new ListNode(Integer.parseInt(String.valueOf(sum.charAt(i))));
            cur = cur.next;
        }
        return node.next;
    }

    public static String reaser(ListNode node) {

        Stack<String> stack = new Stack();
        while (node != null) {
            stack.add(String.valueOf(node.val));
            node = node.next;
        }
        StringBuilder sb = new StringBuilder();
        while (stack.size() > 0) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }

    public static int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        //这样循环会使每次最后一次循环刚好是要删除的元素的上一个元素
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        //该元素的下一个数据就是要删除的元素，直接用该元素的下一个元素的下一个元素进行删除
        cur.next = cur.next.next;
        return dummy.next;
    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}